package lc.q101_150;

import lc.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class Q102 {

    public List<List<Integer>> levelOrder(TreeNode root) {
        // 深度优先
        if (root == null) {
            return null;
        }
        List<List<Integer>> results = new ArrayList<>();
        dfs(root, 0, results);
        return results;
    }

    private void dfs(TreeNode root, int level, List<List<Integer>> results) {
        if (root == null) {
            return;
        }
        int size = results.size();
        for (int i = size; i <= level; i++) {
            results.add(new ArrayList<>());
        }
        List<Integer> integers = results.get(level);
        integers.add(root.val);
        dfs(root.left, level + 1, results);
        dfs(root.right, level + 1, results);
    }

}
